package codetop.microsoft.T752;

import java.util.*;

/**
 * @Author: 18362
 * @Create: 2022-08-18 22:39:17 星期四
 */
class Solution {
    private Set<String> deadSet = new HashSet<>();
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target))
            return 0;
        deadSet.addAll(Arrays.asList(deadends));
        if (deadSet.contains(target) || deadSet.contains("0000"))
            return -1;
        return bfs("0000", target);
    }

    private int bfs(String start, String target) {
        Queue<String> dq1 = new LinkedList<>(), dq2 = new LinkedList<>();
        Map<String, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        dq1.offer(start);
        dq2.offer(target);
        map1.put(start, 0);
        map2.put(target, 0);
        while (!dq1.isEmpty() && !dq2.isEmpty()) {
            int t = -1;
            if (dq1.size() <= dq2.size())
                t = updateBfs(dq1, map1, map2);
            else
                t = updateBfs(dq2, map2, map1);
            if (t != -1)
                return t;
        }
        return -1;
    }

    private int updateBfs(Queue<String> dq, Map<String, Integer> cur, Map<String, Integer> other) {
        int size = dq.size();
        for (int k=0; k<size; ++k) {
            String front = dq.poll();
            int step = cur.get(front);
            char[] chars = front.toCharArray();
            for (int i=0; i<chars.length; ++i) {
                for (int j=1; j<=9; j+=8) {
                    int curNum = chars[i] - '0';
                    int nextNum = (curNum + j) % 10;
                    char[] clone = chars.clone();
                    clone[i] = (char) (nextNum + '0');
                    String s = String.valueOf(clone);
                    if (deadSet.contains(s) || cur.containsKey(s))
                        continue;
                    if (other.containsKey(s))
                        return other.get(s) + 1 + step;
                    else {
                        dq.offer(s);
                        cur.put(s, step+1);
                    }
                }
            }
        }
        return -1;
    }
}